namespace IOFaster {
  static constexpr int MAX_SIZE = 1 << 20;
  static constexpr char NEGATIVE = '-';
  static char gbuf[MAX_SIZE], *p1 = gbuf, *p2 = gbuf;
  static char pbuf[MAX_SIZE], *p3 = pbuf;
  static char pval[40];

  inline char gc() {
    return p1 == p2 && (p2 = (p1 = gbuf) + fread (gbuf, 1, MAX_SIZE, stdin), p1 == p2) ? EOF : *p1++;
  }
  inline void pc(const char& c) {
    if (p3 - pbuf == MAX_SIZE) fwrite(pbuf, 1, MAX_SIZE, stdout), p3 = pbuf;
    *p3++ = c;
  }
  inline void flush() {
    if (p3 != pbuf) fwrite(pbuf, 1, p3 - pbuf, stdout);
    p3 = pbuf;
  }

  template <class T> inline bool read(T &x) {
    x = 0; char c = gc(); bool f(0);
    while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = gc(); }
    while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = gc(); if (f) x = -x; return true;
  }
  template <class T> inline void write(T x) {
    int top = 0;
    x < 0 ? pc(NEGATIVE), x = -x : x;
    do {
      pval[top++] = static_cast<char>(x % 10 + '0');
      x /= 10;
    } while (x);
    while (top) pc(pval[--top]);
  }

  inline void write(const char &x) {
    pc(x);
  }
  inline void write(const char &&x) {
    pc(x);
  }

  inline void write(const string &x) {
    for (auto &ch : x) {
      pc(ch);
    }
  }
  inline void write(const string &&x) {
    for (auto &ch : x) {
      pc(ch);
    }
  }

  template <> inline bool read<string>(string &x) {
    char c = gc();
    while ((c == ' ' || c == '\n') && c != EOF) {
      c = gc();
    }
    if (c == EOF) {
      return false;
    }
    do {
      x += c;
      c = gc();
    } while (c != ' ' && c != '\n' && c != EOF);
    return true;
  }
}
// flush(); 一定要在输出的最后加上这个
using namespace IOFaster;